【题解】 [ZJOI2009]狼和羊的故事 网络流 luoguP2598 | Qiuly's blog!

【题解】 [ZJOI2009]狼和羊的故事 网络流 luoguP2598

Posted on | Edited on | In | Comments:

这题真的是裸的网络流……连我这种制杖都可以立刻想到正解。

如果不考虑领地问题的话，这显然是一道很裸的最小割———割断最少的边使 $S$ 和 $T​$ 不连通。

但是现在有了领地的问题……就是说限制了有些格子是一起的，不能被割开。

既然不能被割开，就连一条 $inf$ 的边啊，这样就割不开了啊。

于是我们可以让 $S$ 向所有的狼的领地连一条边权为 $inf$ 的边，然后所有的羊的领地向 $T$ 连一条边权为 $inf$ 的边。然后就是网格边连边了……

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

#define A printf("A")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define id(x,y) (((x)-1)*m+(y))

const int N=1e5+2;
const int inf=1e9+9;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};

int n,m,s,t;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

namespace Dinic{

    std::queue<int> q;
    struct Edge{int nxt,to,val;}G[N<<1];
    int cnt(1),dep[N],head[N];

    inline void add(int u,int v,int w){
        G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].val=w,head[u]=cnt;
        G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].val=0,head[v]=cnt; 
    }

    inline bool bfs(){
        memset(dep,0,sizeof(dep)); 
        q.push(s);dep[s]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=head[x];i;i=G[i].nxt){
                int y=G[i].to;
                if(dep[y]||G[i].val<=0)continue;
                dep[y]=dep[x]+1,q.push(y);
            } 
        }return dep[t];
    } 
    inline int dfs(int x,int flow){
        if(x==t||!flow)return flow;
        int used=0,rlow;
        for(int i=head[x];i;i=G[i].nxt){
            int y=G[i].to;
            if(dep[y]==dep[x]+1&&G[i].val){
                used+=(rlow=dfs(y,min(G[i].val,flow-used)));
                G[i].val-=rlow,G[i^1].val+=rlow;
            }
        }if(!used)dep[x]=-1;
        return used;
    }

    inline int dinic(){
        int maxflow=0;
        while(bfs())maxflow+=dfs(s,inf);
        return maxflow;
    }
}

int main(){
    IN(n),IN(m);s=n*m+1,t=n*m+2;
    for(int i=1;i<=n;++i)
    	for(int j=1;j<=m;++j){
    		int a;IN(a);
    		if(a==1)Dinic::add(s,id(i,j),inf);
    		if(a==2)Dinic::add(id(i,j),t,inf);
    	}	
    for(int i=1;i<=n;++i)
    	for(int j=1;j<=m;++j)
    		for(int k=0;k<4;++k){
 	   			int tx=i+dx[k],ty=j+dy[k];
 	   			if(tx<1||tx>n||ty<1||ty>m)continue;
 	   			Dinic::add(id(i,j),id(tx,ty),1);
            }
    printf("%d\n",Dinic::dinic());
    return 0;
}

本文标题:【题解】 [ZJOI2009]狼和羊的故事 网络流 luoguP2598

文章作者:Qiuly

发布时间:2019年03月11日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/03/11/[题解]luoguP2598/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。